ListNode *sortList(ListNode *head) {
	if (head == nullptr)
		return nullptr;
	else
		return MergeSort(head);
}

ListNode *MergeSort(ListNode *head) {
	if (head->next == nullptr)
		return head;
	ListNode *pre = nullptr, *p = head, *q = head;
	while (p && q) {
		pre = p;
		p = p->next;
		q = q->next;
		if (q != nullptr)
			q = q->next;
	}
	pre->next = nullptr;
	ListNode *l = MergeSort(head);
	ListNode *r = MergeSort(p);
	return Merge(l, r);
}
ListNode *Merge(ListNode *A, ListNode *B) {
	ListNode *p = A, *q = B, *r, *t;
	r = new ListNode(0);
	t = r;
	while (p && q) {
		if (p->val < q->val) {
			r->next = p;
			r = r->next;
			p = p->next;
		} else {
			r->next = q;
			r = r->next;
			q = q->next;
		}
	}
	if (p != nullptr)
		r->next = p;
	else
		r->next = q;
	return t->next;
}
